Longest Common Subsequence এবং 0/1 Knapsack Problem উভয়ই কম্পিউটার বিজ্ঞানে বিখ্যাত বেসিক সমস্যা যা ডায়নামিক প্রোগ্রামিংয়ের মাধ্যমে সমাধান করা হয়। নিচে প্রতিটি সমস্যার বিশ্লেষণ এবং উদাহরণ দেয়া হলো:
১. Longest Common Subsequence (LCS)
Longest Common Subsequence সমস্যায় দুটি স্ট্রিং দেয়া থাকে, এবং আমাদের কাজ হলো সবচেয়ে বড় সাবসিকোয়েন্সটি খুঁজে বের করা, যা উভয় স্ট্রিংয়ে উপস্থিত থাকে।
উদাহরণ
যদি আমাদের দুটি স্ট্রিং থাকে:
X = "ABCBDAB"Y = "BDCAB"
তাহলে এই দুটি স্ট্রিংয়ের মধ্যে Longest Common Subsequence হবে BDAB, যার দৈর্ঘ্য ৪।
সমাধান পদ্ধতি
আমরা ডায়নামিক প্রোগ্রামিং ব্যবহার করে এই সমস্যাটি সমাধান করতে পারি। প্রথমে একটি টেবিল তৈরি করি, যেখানে LCS[i][j] মানে হলো X এর প্রথম i অক্ষর এবং Y এর প্রথম j অক্ষরের মধ্যে Longest Common Subsequence এর দৈর্ঘ্য।
- যদি
X[i-1] == Y[j-1], তাহলেLCS[i][j] = LCS[i-1][j-1] + 1 - অন্যথায়,
LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])
কোড (Python):
def lcs(X, Y):
m, n = len(X), len(Y)
LCS = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if X[i - 1] == Y[j - 1]:
LCS[i][j] = LCS[i - 1][j - 1] + 1
else:
LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])
return LCS[m][n]
টাইম এবং স্পেস কমপ্লেক্সিটি
- টাইম কমপ্লেক্সিটি: O(m * n), যেখানে
mএবংnযথাক্রমেXএবংYএর দৈর্ঘ্য। - স্পেস কমপ্লেক্সিটি: O(m * n), কারণ টেবিল সংরক্ষণ করতে অতিরিক্ত মেমোরি লাগে।
২. 0/1 Knapsack Problem
0/1 Knapsack Problem সমস্যায় একটি ব্যাগের নির্দিষ্ট ওজন সীমা দেয়া থাকে এবং বিভিন্ন আইটেম দেয়া থাকে। প্রতিটি আইটেমের ওজন এবং মান (value) দেয়া থাকে। আমাদের কাজ হলো ব্যাগটি ওজন সীমা পূরণ না করেই আইটেমগুলোর মূল্য সর্বাধিক করা। এখানে 0/1 বলতে বোঝায়, প্রতিটি আইটেম হয় ব্যাগে থাকবে না হয় থাকবে না (ভগ্নাংশ নয়)।
উদাহরণ
ধরা যাক আমাদের কাছে ৪টি আইটেম আছে:
- আইটেম:
[{weight: 1, value: 10}, {weight: 3, value: 40}, {weight: 4, value: 50}, {weight: 5, value: 70}] - ব্যাগের সর্বোচ্চ ওজন:
8
এই ক্ষেত্রে, সর্বাধিক মূল্য অর্জন করতে ব্যাগে কিছু নির্দিষ্ট আইটেম রাখতে হবে।
সমাধান পদ্ধতি
ডায়নামিক প্রোগ্রামিং ব্যবহার করে এই সমস্যাটি সমাধান করা যায়। প্রথমে একটি টেবিল তৈরি করি, যেখানে dp[i][w] অর্থাৎ প্রথম i আইটেম এবং ব্যাগের ওজন w এর মধ্যে সর্বাধিক মূল্য।
- যদি
weight[i] > wঅর্থাৎ আইটেমের ওজনwএর বেশি হয়, তাহলেdp[i][w] = dp[i-1][w] - অন্যথায়,
dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - weight[i]])
কোড (Python):
def knapsack(weights, values, W):
n = len(values)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, W + 1):
if weights[i - 1] <= w:
dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][W]
টাইম এবং স্পেস কমপ্লেক্সিটি
- টাইম কমপ্লেক্সিটি: O(n * W), যেখানে
nহলো আইটেমের সংখ্যা এবংWহলো ব্যাগের সর্বোচ্চ ওজন। - স্পেস কমপ্লেক্সিটি: O(n * W), কারণ টেবিল সংরক্ষণ করতে অতিরিক্ত মেমোরি প্রয়োজন।
উপসংহার
- Longest Common Subsequence: দুটি স্ট্রিংয়ের মধ্যে সবচেয়ে বড় মিল খুঁজতে ব্যবহৃত হয়।
- 0/1 Knapsack Problem: সর্বাধিক মূল্য অর্জনের জন্য নির্দিষ্ট ওজন সীমার মধ্যে আইটেম বাছাই করতে ব্যবহৃত হয়।
দুটি সমস্যাই ডায়নামিক প্রোগ্রামিংয়ের গুরুত্বপূর্ণ সমস্যা এবং বিভিন্ন ক্ষেত্রে প্রয়োজনীয় সমাধান প্রদান করতে সক্ষম।
